#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <set>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cassert>
#include <utility>

using namespace std;

#define EPS 1E-8

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forv(i, a) for (int i = 0; i < int(a.size()); i++)
#define fors(i, a) for (int i = 0; i < int(a.length()); i++)
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
#define VI vector<int>
#define VS vector<string>

#define norm(a) sort(all(a)); a.erase(unique(all(a)), a.end());
#define num(a, v) (int)(lower_bound(all(a), v) - a.begin())

#define C_IN_FILE "input.txt"
#define C_OUT_FILE "output.txt"

typedef vector<int> line;
typedef vector<line> matrix;
typedef map<int, int> function;
typedef map<int, vector<int> > graph;

matrix a;
function fRenum, fIden, fIdenColoring, fSimpleColoring;

void outdata() {
}

void appendFunction(const matrix& a, function& f) {
    forv(i, a) {
        forv(j, a[i]) {
            int z = a[i][j];
            if (f.count(z) == 0) {
                f[z] = 0;
            }
        }
    }
}

int renumeration(const matrix& a, function& f) {
    int cur = 0;
    f.clear();
    forv(i, a) {
        forv(j, a[i]) {
            int z = a[i][j];
            if (f.count(z) == 0) {
                f[z] = cur++;
            }
        }
    }
    appendFunction(a, f);
    return cur - 1;
}

void identification(const matrix& a, function& f, const vector<int>& clazz, int col) {
    if ((int)clazz.size() <= 1) return ;
    vector<int> nums;
    forv(i, clazz) nums.pb(a[clazz[i]][col]);
    norm(nums);
    if ((int)nums.size() > 1) {
        forv(i, nums) {
            int z = nums[i];
            if (f.count(z) == 0) {
                int newval = (int)f.size();
                f[z] = newval;
            }
        }
    }
    vector<pair<int, int> > clnum;
    forv(i, clazz) clnum.pb(mp(a[clazz[i]][col], clazz[i]));
    norm(clnum);
    vector<int> cclass;
    forv(i, clnum) {
        if (i > 0 && clnum[i].first != clnum[i - 1].first) {
            identification(a, f, cclass, col + 1);
            cclass.clear();
        }
        cclass.pb(clnum[i].second);
    }
    identification(a, f, cclass, col + 1);
}

int identification(const matrix& a, function& f) {
    f.clear();
    vector<int> clazz(a.size());
    forv(i, a) clazz[i] = i;
    identification(a, f, clazz, 0);
    int res = max(1, (int)f.size());
    appendFunction(a, f);
    return res - 1;
}

int colorGraph(const graph& g, function& f, set<int>& used, map<int, int>& d) {
    int bv = -1, mind = (int)g.size();
    for(graph::const_iterator it = g.begin(); it != g.end(); ++it) {
        int v = it->first;
        if (used.count(v) == 0) {
            int cd = d[v];
            if (mind > cd) {
                bv = v;
                mind = cd;
            }
        }
    }
    if (bv == -1) return 0;
    used.insert(bv);
    vector<int> next = g.find(bv)->second;
    forv(i, next) {
        d[next[i]]--;        
    }
    int res = colorGraph(g, f, used, d);
    vector<int> colors;
    forv(i, next) {
        if (f.count(next[i]) != 0) {
            colors.pb(f[next[i]]);
        }
    }
    norm(colors);
    int cur = 0, resCol = -1;
    forv(i, colors) {
        if (cur != colors[i]) {
            break;
        } else {
            cur++;
        }
    }
    resCol = cur;
    f[bv] = resCol;
    res = max(res, resCol);
    return res;     
}

int grundyFunction(graph& g, function& f) {
    f.clear();
    map<int, int> d;
    for(graph::iterator it = g.begin(); it != g.end(); ++it) {
        norm(it->second);
        d[it->first] = (int)it->second.size();
    }
    set<int> used;
    int res = colorGraph(g, f, used, d);
    appendFunction(a, f);
    return res;
}

int simpleGraphColoring(const matrix& a, function& f) {
    graph g;
    forv(i, a) {
        forn(j, i) {
            forv(t, a[i]) {
                if (a[i][t] != a[j][t]) {
                    int u = a[i][t];
                    int v = a[j][t];
                    g[u].pb(v);
                    g[v].pb(u);
                    break;
                }
            }
        }
    }
    return grundyFunction(g, f);
}

void identificationGraphColoring(const matrix& a, graph& g, const vector<int>& clazz, int col) {
    if ((int)clazz.size() <= 1) return ;
    vector<int> nums;
    forv(i, clazz) nums.pb(a[clazz[i]][col]);
    norm(nums);
    forv(i, nums) {
        forn(j, i) {
            int u = nums[i];
            int v = nums[j];
            g[u].pb(v);
            g[v].pb(u);
        }
    }
    vector<pair<int, int> > clnum;
    forv(i, clazz) clnum.pb(mp(a[clazz[i]][col], clazz[i]));
    norm(clnum);
    vector<int> cclass;
    forv(i, clnum) {
        if (i > 0 && clnum[i].first != clnum[i - 1].first) {
            identificationGraphColoring(a, g, cclass, col + 1);
            cclass.clear();
        }
        cclass.pb(clnum[i].second);
    }
    identificationGraphColoring(a, g, cclass, col + 1);
}

int identificationGraphColoring(const matrix& a, function& f) {
    graph g;
    vector<int> clazz(a.size());
    forv(i, a) clazz[i] = i;
    identificationGraphColoring(a, g, clazz, 0);
    return grundyFunction(g, f);
}

void outFunction(const function& f) {
    for(function::const_iterator it = f.begin(); it != f.end(); ++it) {
        printf("\t%d -> %d\n", it->first, it->second);
    }    
}

void solve() {
    cerr << "renumeration" << endl;
    printf("renumeration %d\n", renumeration(a, fRenum));
    outFunction(fRenum);
    cerr << "identification" << endl;
    printf("identification %d\n", identification(a, fIden));
    outFunction(fIden);
    cerr << "simpleGraphColoring" << endl;
    printf("simpleGraphColoring %d\n", simpleGraphColoring(a, fSimpleColoring));
    outFunction(fSimpleColoring);
    cerr << "identificationGraphColoring" << endl;
    printf("identificationGraphColoring %d\n", identificationGraphColoring(a, fIdenColoring));
//    printf("Yes\n%d\n", identificationGraphColoring(a, fIdenColoring));
    outFunction(fIdenColoring);
}

bool isDiagnostic(const matrix& a) {
    forv(i, a) {
        forn(j, i) {
            if (a[i] == a[j]) {
                return false;
            }
        }
    }
    return true;
}

void readdata() {
    int n, m;
    assert(scanf("%d%d", &n, &m) == 2);
    a = matrix(n, line(m));
    forn(i, n) {
        forn(j, m) {
            assert(scanf("%d", &a[i][j]) == 1);
            assert(0 <= a[i][j] && a[i][j] <= (int)1e+9);
        }
    }
    assert(isDiagnostic(a));
}   

int main() {
    readdata();
    solve();
    outdata();
    return 0;
}
